package datastructure.list;

import java.lang.reflect.Array;
import java.util.Iterator;

/**
 * Description：头结点存储元素的单链表
 * Author: zhangc
 * Date：2017/6/26 15:35
 */
public class SingleLinkedList<T> implements List<T> {

    private Node<T> head;
    private Integer length = 0;

    private static class Node<T> {
        private T value;
        private Node<T> next;

        private Node(T value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }


    @Override
    public void append(T element) {
        if (length == 0) {
            head = new Node<>(element);
            length++;
        } else {
            Node<T> temp = head;
            while (temp.next != null)
                temp = temp.next;
            temp.next = new Node<>(element);
            length++;
        }
    }

    @Override
    public void insert(int index, T element) {
        if (index < 0 || index > length)
            throw new IllegalArgumentException("下标越界。。。");
        Node<T> insertNode = new Node<>(element);
        if (length == 0) {
            if (index == 0)
                head = new Node<>(element);
            else
                throw new IllegalArgumentException("下标越界。。。");
        } else if (index == 0) {
            insertNode.next = head;
            head = insertNode;
        } else {
            Node<T> temp = head;
            for (int i = 0; i < index - 1; i++) {
                temp = head.next;
            }
            insertNode.next = temp.next;
            temp.next = insertNode;
        }
        length++;
    }

    @Override
    public T get(int index) {
        if (index < 0 || index >= length)
            throw new IllegalArgumentException("下标越界。。。");
        Node<T> temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp.value;
    }

    @Override
    public T remove(int index) {
        if (index < 0 || index >= length)
            throw new IllegalArgumentException("下标越界。。。");
        Node<T> temp = head;
        T rtnValue;
        if (index == 0) {
            head = head.next;
            rtnValue = temp.value;
        } else {
            for (int i = 0; i < index - 1; i++) {
                temp = temp.next;
            }
            rtnValue = temp.next.value;
            temp.next = temp.next.next;
        }
        length--;
        return rtnValue;
    }

    @Override
    public List<T> subList(int start, int end) {
        if (start > end || start < 0 || end >= length)
            throw new IllegalArgumentException("下标越界。。。");
        List<T> list = new SingleLinkedList<>();
        for (int i = start; i < end; i++) {
            list.append(get(i));
        }
        return list;
    }

    @Override
    public void clear() {
        length = 0;
        head = null;
    }

    @Override
    public int length() {
        return length;
    }

    @Override
    public boolean contains(T element) {
        Node<T> temp = head;
        boolean contains = false;
        // 这里容易误写成 temp.next != null
        while (temp != null) {
            if (element.equals(temp.value))
                contains = true;
            temp = temp.next;
        }
        return contains;
    }


    @SuppressWarnings("unchecked")
    @Override
    public Iterator<T> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator {
        private Integer index = 0;

        @Override
        public boolean hasNext() {
            // 此处 易错，易犯 index < length -1 的错误。
            return index < length;
        }

        @Override
        public T next() {
            return get(index++);
        }
    }

    @SuppressWarnings("unchecked")
    @Override
    public T[] toArray(T[] array) {
        if (array.length < length)
            array = (T[]) Array.newInstance(array.getClass().getComponentType(), length);
        for (int i = 0; i < length; i++) {
            array[ i ] = get(i);
        }
        return array;
    }

    @Override
    public Object[] toArray() {
        Object[] array = new Object[ length ];
        for (int i = 0; i < length; i++) {
            array[ i ] = get(i);
        }
        return array;
    }


    public static <T extends Comparable<? super T>> void listSort(SingleLinkedList<T> list) {

        if (list.head == null || list.head.next == null)
            return;
        Node<T> otherHead = list.head.next;
        Node<T> last, temp;
        list.head.next = null;
        while (otherHead != null) {
            temp = otherHead;
            otherHead = otherHead.next;
            if (temp.value.compareTo(list.head.value) < 0) {
                temp.next = list.head;
                list.head = temp;
            } else {
                last = list.head;
                while (last.next != null && last.next.value.compareTo(temp.value) < 0) {
                    last = last.next;
                }
                temp.next = last.next;
                last.next = temp;
            }
        }
    }

    @Override
    public String toString() {
        return "SingleLinkedList{" +
                "head=" + head +
                ", length=" + length +
                '}';
    }
}
